package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/description/
 * @create 2025/9/14 16:18
 * @since JDK17
 */

public class Solution37 {
    int n, max, cnt;
    TreeNode ans;

    // 求出最大的深度和存在几个结点到达了该深度
    void f(TreeNode root, int cur) {
        if (cur == max) {
            n++;
        }
        if (cur > max) {
            n = 1;
            max = cur;
        }
        if (root.left != null) {
            f(root.left, cur + 1);
        }
        if (root.right != null) {
            f(root.right, cur + 1);
        }
    }

    int f2(TreeNode root, int cur) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        if (cur == max) {
            res++;
        }
        res += f2(root.left, cur + 1);
        res += f2(root.right, cur + 1);
        if (res == n && ans == null) {
            ans = root;
        }
        return res;
    }

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        f(root, 1);
        f2(root, 1);
        return ans;
    }
}
